package 全排列;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 全排列 II  给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * @date 2022/11/19 11:19
 */
public class Demo47 {

    LinkedList<Integer> path=new LinkedList<>();
    HashMap<Integer,Integer> mapper=new HashMap<>();
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            mapper.put(nums[i],mapper.getOrDefault(nums[i],0)+1);

        }
        int[] ints = Arrays.stream(nums).distinct().toArray();
        backTrack(nums,ints,0);
        return res;
    }

    private void backTrack(int[] originNums,int[] nums, int startIndex) {
        if(originNums.length==path.size()){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            int finalI = i;
            List<Integer> collect = path.stream().filter(s -> s == nums[finalI]).collect(Collectors.toList());
            if(collect.size()==mapper.get(nums[i])){
                continue;
            }
            path.add(nums[i]);
            backTrack(originNums,nums,0);
            path.removeLast();
        }
    }
}
